Masala #1027
Maksimal segmentlar yig'indisi
Qulmamat massivdagi so'rovlar haqidagi masalalarni juda yaxshi ko'radi.
Bir kun u juda mashhur masalaga duch keldi. \(n\) ta elementli \(a\) massiv beriladi va \(q\) ta \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlar mavjud. Har bir so'rovda massivning \(l_i-\) elementidan \(r_i-\) elementigacha bo'lgan barcha sonlarning yig'indisini hisoblash talab etiladi.
Bunday vazifa Qulmamatga juda zerikarli tuyildi. U surovlarga javob berishidan oldin massiv elementlarini aralashtirib, barcha so'rovlarga javoblar yig'indisi maksimal darajaga keltirishga qaror qildi. Sizning vazifangiz ushbu maksimal miqdorni hisoblashdan iborat.
Birinchi satrda ikkita \(n(1\leq n\leq 2000000)\) va \(q(1\leq q\leq 2000000)\) butun sonlar. Kiyingi satrda \(n\) ta \(a_i(-10^9\leq a_i\leq 10^9)\) massiv elementlari beriladi va kiyingi \(q\) satrda \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlari beriladi.
Yagona satrda masalani javobini \(-\) massiv elementlari tartibini o'zgartirganingizdan so'ng so'rovlarga javoblarning maksimal yig'indisini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 2 3 5 1 2 2 3 |
15 |
Birinchi testda [2, 3, 5] massivni [2, 5, 3] ko'rinishiga keltirsangiz so'rovlar \(a_{[1..2]}=2+5=7\) va \(a_{[2..3]}=5+3=8\) yig'indisi 15 ga teng.
Telegram kanalimizga obuna bo'ling